import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class AgentDFS implements Agent {

	private State _state;
	private int stateExpansions = 0;
	private int terminals = 0;
	private int depth = 0;
	private boolean foundSolution;
	private List<State> _visitedStates;
	
	int solutionIndex = 0;
	private List<Node> _solutionNodes;
	

	public AgentDFS()
	{
		_state = new State();
		_visitedStates = new ArrayList<State>();
		_solutionNodes = new ArrayList<Node>();
	}
	
	/*
		init(Collection<String> percepts) is called once before you have to select the first action. Use it to find a plan. 
		Store the plan and just execute it step by step in nextAction.
	*/
	public void init(Collection<String> percepts) 
	{
		/*
		Possible percepts are:
		- "(SIZE x y)" denoting the size of the environment, where x,y are integers
		- "(HOME x y)" with x,y >= 1 denoting the initial position of the robot
		- "(ORIENTATION o)" with o in {"NORTH", "SOUTH", "EAST", "WEST"} denoting the initial orientation of the robot
		- "(AT o x y)" with o being "DIRT" or "OBSTACLE" denoting the position of a dirt or an obstacle
		Moving north increases the y coordinate and moving east increases the x coordinate of the robots position.
		The robot is turned off initially, so don't forget to turn it on.
		*/
		
		Pattern perceptNamePattern = Pattern.compile("\\(\\s*([^\\s]+).*");
		for (String percept:percepts) 
		{
			Matcher perceptNameMatcher = perceptNamePattern.matcher(percept);
			if (perceptNameMatcher.matches()) 
			{
				String perceptName = perceptNameMatcher.group(1);
	
				if (perceptName.equals("HOME")) 
				{
					Matcher m = Pattern.compile("\\(\\s*HOME\\s+([0-9]+)\\s+([0-9]+)\\s*\\)").matcher(percept);
					if (m.matches()) 
					{
						System.out.println("robot is at " + m.group(1) + "," + m.group(2));
						int x = Integer.parseInt(m.group(1))-1, y = Integer.parseInt(m.group(2))-1;
						_state.setHome(x, y);
					}
				}
				else if (perceptName.equals("ORIENTATION"))
				{
					Matcher m = Pattern.compile("\\(\\s*(ORIENTATION)\\s+(NORTH|SOUTH|EAST|WEST)\\s*\\)").matcher(percept);
					if (m.matches()) 
					{
						System.out.println("ORIENTATION " + m.group(2));
						//_state.setOrientation(m.group(2));
						_state.initDirIndex(m.group(2));
					}
				}
				else if (perceptName.equals("AT"))
				{
					Matcher m = Pattern.compile("\\(\\s*(AT)\\s+(DIRT|OBSTACLE)\\s+([0-9]+)\\s+([0-9]+)\\s*\\)").matcher(percept);
					if (m.matches()) 
					{
						int x = Integer.parseInt(m.group(3))-1, y = Integer.parseInt(m.group(4))-1;
						if (m.group(2).equals("DIRT"))
						{
							_state.addDirt(x, y);
						}
						else
						{
							_state.addObstacle(x, y);
						}
					}
				}
				else if (perceptName.equals("SIZE"))
				{
					Matcher m = Pattern.compile("\\(\\s*SIZE\\s+([0-9]+)\\s+([0-9]+)\\s*\\)").matcher(percept);
					if (m.matches())
					{
						System.out.println("Environment is " + m.group(1) + "," + m.group(2));
						int width = Integer.parseInt(m.group(1)), height = Integer.parseInt(m.group(2));
						_state.initArea(width, height);
					}
				}
				else 
				{
					System.out.println("other percept:" + percept);
				}
			} 
			else 
			{
				System.err.println("strange percept that does not match pattern: " + percept);
			}
			_state.printState();
		}
		
		System.out.println("Dirt left: " + _state.getDirtLeft());
		
		Node root = new Node(null, _state, "");
		
		DFS(root, 30);
		
		System.out.println("State expansions: " + stateExpansions + ", solution size: " + _solutionNodes.size() + ", terminals: " + terminals);
		for (Node s : _solutionNodes)
		{
			s.state.printState();
			
	
		}
		
		
	}
	
	public void DFS(Node current, int depthLimit)
	{
		_visitedStates.add(current.state);
		if (current.state.goalTest())
		{
			System.out.println("SOLUTION FOUND!!!!");
			current.state.printState();
			foundSolution = true;
		}
		else if (depthLimit == 0)
		{
			terminals++;
			return;
		}
		else
		{
			for (String action : current.state.legalMoves())
			{
				Node child = new Node(current, current.state.getNextState(action), action);
				boolean repeated = false;
				for (State s : _visitedStates)
				{
					
					if (s.hasVisited(child.state))
					{
						//System.out.println("Similar state");
						repeated = true;
					}
				}
				
				if (repeated == false)
				{
					_solutionNodes.add(child);
					current.children.add(child);
					DFS(child, depthLimit-1);
					stateExpansions++;
					if (foundSolution)
					{
						break;
					}
					else
					{
						_solutionNodes.remove(child);
					}
				}
			}	
		}
		
		
	}
	
	public String nextAction(Collection<String> percepts) 
	{
		String action = _solutionNodes.get(solutionIndex).action;
		if (solutionIndex < _solutionNodes.size()-1)
		{
			solutionIndex++;
		}
		return action;
	}
}


























